package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/12/8 20:08
 * @description：https://leetcode-cn.com/problems/maximum-sum-of-3-non-overlapping-subarrays/
 */
public class 三个无重叠子数组的最大和 {
    @Test
    public void test() {
        Solution solution = new Solution();
    }

    class Solution {
        public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
            int[] ans = new int[3];
            int sum1 = 0, sum2 = 0, sum3 = 0;
            int maxSum1Idx = 0, maxSum12Idx1 = 0, maxSum12Idx2 = 0;
            int maxSum1 = 0, maxSum2 = 0, maxSum3 = 0;
            for (int i = 2 * k; i < nums.length; i++) {
                sum1 += nums[i - 2 * k];
                sum2 += nums[i - k];
                sum3 += nums[i];
                if (i >= k * 3 - 1) {
                    if (sum1 > maxSum1) {
                        maxSum1 = sum1;
                        maxSum1Idx = i - k * 3 + 1;
                    }
                    if (sum2 + maxSum1 > maxSum2) {
                        maxSum2 = maxSum1 + sum2;
                        maxSum12Idx1 = maxSum1Idx;
                        maxSum12Idx2 = i - k * 2 + 1;
                    }
                    if (sum3 + maxSum2 > maxSum3) {
                        maxSum3 = maxSum2 + sum3;
                        ans[0] = maxSum12Idx1;
                        ans[1] = maxSum12Idx2;
                        ans[2] = i - k + 1;
                    }
                    sum1 -= nums[i - k * 3 + 1];
                    sum2 -= nums[i - k * 2 + 1];
                    sum3 -= nums[i - k + 1];
                }
            }
            return ans;
        }
    }

}
